package com.c2b.algorithm.leetcode.base;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * <a href="https://leetcode.cn/problems/increasing-order-search-tree/">递增顺序搜索树(Increasing Order Search Tree)</a>
 * <p>给你一棵二叉搜索树的 root ，请你 按中序遍历 将其重新排列为一棵递增顺序搜索树，使树中最左边的节点成为树的根节点，并且每个节点没有左子节点，只有一个右子节点。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：root = [5,3,6,2,4,null,8,1,null,null,null,7,9]
 *      输出：[1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]
 *
 * 示例 2：
 *      输入：root = [5,1,7]
 *      输出：[1,null,5,null,7]
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>树中节点数的取值范围是 [1, 100]</li>
 *     <li>0 <= Node.val <= 1000</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/11/17 13:46
 */
public class LC0897IncreasingOrderSearchTree_S {

    static class Solution {

        private TreeNode resNode;

        public TreeNode increasingBST(TreeNode root) {
            TreeNode dummyRoot = new TreeNode(-1);
            resNode = dummyRoot;
            inorder(root);
            return dummyRoot.right;
        }

        public void inorder(TreeNode node) {
            if (node == null) {
                return;
            }
            // 左
            inorder(node.left);
            // 根
            resNode.right = node;
            node.left = null;
            resNode = node;
            // 右
            inorder(node.right);
        }

        public TreeNode increasingBST2(TreeNode root) {
            TreeNode dummyRoot = new TreeNode(-1);
            TreeNode prevNode = dummyRoot;
            Deque<TreeNode> stack = new ArrayDeque<>();
            while (root != null || !stack.isEmpty()) {
                while (root != null) {
                    stack.addFirst(root);
                    root = root.left;
                }
                TreeNode currNode = stack.pollFirst();
                root = currNode.right;
                // 避免出现循环依赖
                currNode.left = null;
                currNode.right = null;

                prevNode.right = currNode;
                prevNode.left = null;

                prevNode = prevNode.right;

            }
            return dummyRoot.right;
        }
    }

    public static void main(String[] args) {
        TreeNode root1 = new TreeNode(5);
        root1.left = new TreeNode(3);
        root1.left.left = new TreeNode(2);
        root1.left.left.left = new TreeNode(1);
        root1.left.right = new TreeNode(4);
        root1.right = new TreeNode(6);
        root1.right.right = new TreeNode(8);
        root1.right.right.left = new TreeNode(7);
        root1.right.right.right = new TreeNode(9);

        TreeNode root2 = new TreeNode(2);
        root2.left = new TreeNode(1);
        root2.right = new TreeNode(4);
        root2.right.left = new TreeNode(3);

        Solution solution = new Solution();
        TreeNode.printTree(solution.increasingBST(root1));
        TreeNode.printTree(solution.increasingBST(root2));


    }
}
